package org.example.leetcode;

import org.omg.CORBA.INTERNAL;
import org.omg.PortableInterceptor.INACTIVE;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @version 1.0.0
 * @author: lynn
 * @description:
 * @date: 2021/8/9 17:19
 */
public class LC60 {

    public static void main(String[] args) {
        LC60 lc=new LC60();
        int n=3;
        int k=3;
        System.out.println(lc.getPermutation(n,k));
    }

    /**
     *    1 {2,3,4}  {2,3,4} 代表组合
     *    2 {1,3,4}
     *    3 {1,2,4}
     *    4 {1,2,3}
     *
     *    res 1 2 3 4
     *   fact 1 1 2 6
     *   k=17, k`=16
     *   i=4 index=17/6=2 k`=17%6=5;
     *   i=3 index=5/2=2  k`=5%2=1;
     *   i=2 index=1/1=1 k`=1%1=0;
     *   i=1 index=0/1=0; k`=0%1=0;
     */

    //fixme https://www.bilibili.com/video/BV18K4y1a7R3?from=search&seid=5161368432883752840
    public String getPermutation(int n, int k) {
        int[] fact=new int[n];
        fact[0]=1;
        for (int i=1;i<n;i++){
            fact[i]=i*fact[i-1];
        }
        List<Integer> res=new ArrayList<>();
        for (int i = 1; i <=n ; i++) {
            res.add(i);
        }
        k--;//第k个
        StringBuilder sb=new StringBuilder();
        for (int i = n-1; i >=0 ; i--) {
            int idx=k/fact[i];
            sb.append(res.get(idx));
            res.remove(idx);
            k%=fact[i];
        }
        return sb.toString();
    }
}
